The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Many Internet Service Providers (ISPs), network administrators, and network operators, among others, configure packet switching routers deployed in networks they manage to use an interior gateway protocol to exchange routing information between the routers. Many network equipment manufacturers and vendors sell routers capable of exchanging routing information with other routers in a network using an interior gateway protocol.
There are two main classes of interior gateway protocols: distance-vector routing protocols and link-state routing protocols. In typical implementations of a link-state routing protocol, each router in a network discovers neighboring routers in the network and establishes an adjacency relationship with each neighboring router. Such neighboring router(s) are often referred to as “adjacencies”. The router periodically sends an advertisement message to each adjacency that may include an identification of each of the advertising router's network links, and for each identified link, the state of the link, the metric cost of the advertising router's interface to the link, and any neighboring routers connected to the link.
Typically, each router receiving an advertisement floods the advertisement to all of its own adjacencies (except to the router from which the advertisement was received). Each router stores information from each advertisement the router receives in a link-state database. Each router maintains its own copy of the link-state database in a computer memory of the router. Ideally, each router in the network receives the advertisements sent by every other router in the network and each link-state database in each router converges to same representation of the state of the network. Each router in the network uses information in its link-state database to construct a topology of the network representing the shortest (lowest cost) path to every other router in the network. Such topology is typically constructed using a shortest path first algorithm. A data representation of the constructed topology commonly referred to as a routing table is also stored in the router's memory. Each router uses its routing table to forward network data packets the router receives onto destinations in the network.
Because each router's link-state database stores information about every other router in the network, the computer memory size of each link-state database at each router increases as the number of routers in the network increases. The greater the size of the link-state database at a router, the more computer memory the router needs to store the link-state database and the more processing resources the router needs to calculate a topology of the network in a constant or near constant amount of time. Thus, adding a router to a network has an adverse impact on the computing resource requirements of the existing routers in the network.
Increasingly, network services provide a network topology dependent service other than packet forwarding. For example, there are standardization efforts underway to provide peer-to-peer (P2P) applications in a network with information about the network to perform better-than-random initial peer selection. As another example, an Internet Service Provider (ISP) may deploy a network topology dependent service in its networks to support other non-routing network applications such as Network Address Translation (NAT), Deep Packet Inspection (DPI), video monitoring, mobility, etc.
For such network topology dependent services to provide information about the network to other network applications, the services may require a topology view of the network. One approach to providing a topology view of the network to a network topology dependent service is to have the service participate in the link-state protocol used by the network. In this approach, the service establishes adjacencies with neighboring routers, collects link-state advertisements as part of normal link-state protocol operation and can obtain information about the state and topology of the network and use the obtained information for providing a network topology dependent service. However, because adding a network element that participates in the link-state protocol to a network increases the size of the link-state database at each router in the network, each network topology dependent service added to a network adds to the computing resource requirements of all routers in the network. Furthermore, the other routers in the network may include the service in their calculated packet forwarding paths, potentially overwhelming the service with network traffic to be forwarded.